import Foundation


public struct Test_DynamicProgram {
    
    // MARK: - 爬楼梯问题
    /// 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢
    /**
     dp[0] = 1  --> 站在起点，只能有一种方式（什么都不做）
     dp[1] = 1  --> 到达第一阶，只有一种方式（爬 1 阶）

     状态转移：
     dp[2] = dp[1] + dp[0] = 1 + 1 = 2  --> 到达第二阶可以从第 1 阶或第 0 阶
     dp[3] = dp[2] + dp[1] = 2 + 1 = 3  --> 到达第三阶可以从第 2 阶或第 1 阶
     dp[4] = dp[3] + dp[2] = 3 + 2 = 5  --> 到达第四阶可以从第 3 阶或第 2 阶
     dp[5] = dp[4] + dp[3] = 5 + 3 = 8  --> 到达第五阶可以从第 4 阶或第 3 阶

     */
    public static func climbStairs(_ n: Int) -> Int {
        // 如果楼梯只有 0 或 1 阶，直接返回 1
        if n == 0 || n == 1 {
            return 1
        }
        // 用两个变量存储到达n-1 和 n-2的方法数
        var dp1 = 1
        var dp2 = 2
        
        for _ in 3...n {
            let dp3 = dp1 + dp2
            dp1 = dp2
            dp2 = dp3
        }
        return dp2
    }
    
    public static func climbStairs2(_ n: inout Int) -> Int {
        var memo = [Int: Int]()
        return climbStairsHelper(n, &memo)
    }
    
    static func climbStairsHelper(_ n: Int, _ memo: inout [Int: Int]) -> Int {
        // 如果已经计算过，直接返回结果
        if let result = memo[n] {
            return result
        }
        
        if n == 1 {
            return 1
        }
        if n == 2 {
            return 2
        }
        let result = climbStairsHelper(n - 1,  &memo) + climbStairsHelper(n - 2, &memo)
        memo[n] = result
        return result
    }
    
}
